1. Field of the Invention
This invention relates combinatorial auctions, reverse auctions and exchanges, and, more particularly, to determining which combination of bids in a combinatorial auction, reverse auction, or exchange has the most favorable exchange of value.
2. Description of Related
In sequential auctions, items are auctioned one at a time. If an agent has preferences over bundles (combinations of items), then bidding in such auctions is difficult. To determine one's valuation for an item, one needs to guess what items one will receive in later auctions. This requires speculation of what the others will bid in the future. This introduces uncertainty and computational cost, both of which reduce efficiency. Furthermore, in auctions with a reasonable number of items, the lookahead becomes intractable, and there is no easy way to bid rationally. Therefore, the future uncertainties of sequential auctions result in inefficiencies making it difficult for rational agents to bid.
An alternative to sequential auctioning of the interdependent items would be to open them all for auction in parallel. However, some of the same problems prevail. For example, when bidding for an item, the bidder does not know its valuation because it depends on which other items the bidder wins, which in turn depends on how others will bid (in sealed-bid auctions this is not known to the bidder, and in open-cry auctions it may become known only later). In parallel auctions, an additional difficulty arises: each bidder would like to wait until the end to see what the going prices will be. If each bidder plans to wait until the end, bidding will not commence. Therefore, parallel auctions also have future uncertainties that result in inefficiencies.
One solution to this problem is to allow bidders to place bids for combinations of individual items instead of only one individual item.
There are, however, situations involving the exchange of items for value in which there may exist synergies in the preferences for, not only, combinations of the items, but also for the quantity of each of the items. For example, an auctioneer holding items wishes to maximize the value obtained through the auction of the items. Bidders may have a willingness to exchange more value for combinations of items and/or selective quantities thereof than they would for individual elements and/or preset quantities thereof of the combination, if considered alone and aggregated. For example, if Q1, Q2, Q3, Q4 and Q5 are quantities, or units, of items A, B, C, D and E, respectively, and if a bidder wishes to acquire one-half of each of item A, item B, and item C, the bidder may have a greater willingness to acquire and pay for this combination then buying the whole of quantities Q1, Q2 and Q3 of items A, B and C. This may occur, for example, where the bidder has no use for the full quantity, or all the units, of a particular item, e.g., electricity markets, equities trading, FCC bandwidth auctions, transportation exchanges, pollution rights auctions, and auctions for airport landing slots. In addition, the bidder may have willingness to pay more than P1+P2+P3 for the full quantity Q1+Q2+Q3 of the three items A, B and C. This effect, which may be bidder-specific, may also be present in a reverse auction context where buyers are the auctioneers, for example, where portions of a construction contract are offered to be bid upon by construction contractors.
To the auctioneer, it is then desirable, to structure an auction to allow a bidder to bid for combinations of items and/or all or part of the quantities thereof, i.e., a multi-unit combinatorial auction, in order to gain the value of their synergies. Similarly, it is desirable for bidders to be able to bid on combinations of items and/or all or part of the quantities thereof. A bidder may be unwilling to bid more than the sum of his or her willingness to pay for all or part of the quantities available for each individual item and, thus, may have to forgo the opportunity to reap the synergistic gains. Alternatively, a bidder may be exposed to risk by overbidding in an eventually unsuccessful attempt to obtain a combination of items and/or all or part of the quantities available therefor.
Conventionally, practical implementations of the class of situations involving superadditive preferences, for example multi-unit combinatorial auctions, have proven difficult because of the complexity of considering numerous possible combinations of bids for items, especially where each bid includes one or more items and for each item a desired quantity thereof. (A special case of a multi-unit combinatorial auction, or exchange, occurs when each item thereof has only a quantity of one (1) associated therewith.) Given the complexity of the calculations, a computer or equivalent device is a virtual necessity to perform the task. Conventionally, computer-implemented methods of selecting winning bids in a multi-unit combinatorial auction involve representing the items, the quantities of each item and the price of each of a plurality of bids in a computer or equivalent and performing particular operations on this data to determine winning bids. However, conventional methods are impractical for many applications.
Winner determination in multi-unit combinatorial auctions means choosing which bids to accept that produce the most favorable exchange of value under the constraint that all or part of the available quantity of each item can be given out. However, presently, no effective means exist for testing all possible combination of bids received in a multi-unit combinatorial auction, reverse auction, or exchange, and for determining from each possible combination which combination of bids produces the most favorable exchange of value.